The demand for networked digital audiovisual systems is expected to grow over the next few years, as business, government and other institutions increasingly turn to digital networks to distribute audiovisual information for education, presentations and reference applications. These customers expect systems that will allow a number of people to be able to view audiovisual information from a server simultaneously, while fully retaining their other network functions. For example, in business computing, most of the major productivity software developers see networked video as an effective means of training and supporting users. Many of these developers have begun including VHS videotapes for training with their software. Now they want to take this a step further by linking the video directly to their software's on-line help resources. Centralizing that support in a video server reduces the cost for customers with many users and ensures that it is properly maintained by the responsible persons.
Networked video presentation systems in business can allow corporate resources, such as sales videos, employee information, and video-based training to be available immediately to all employees from their desks. Similarly, networked video documentation systems will allow institutions of all kinds to maintain multi-user audiovisual databases. One large population of users of such systems are likely to be health care institutions which have extensive audiovisual records. In addition, such databases can be used for on-the-job reference such as revisiting a complex procedure on the manufacturing floor, or creating an on-line archive of TV commercials for an advertising agency.
Audiovisual communication including video conferencing, video mail, and collaborative work, is yet another fast growing business application which requires the support of networked video over Local Area Networks.
The characteristics of video data traffic differ substantially from those of traditional transactional data traffic to the point that Local Area Networks designed primarily to support transactional data applications are not appropriate to effectively support video services. With transactional data applications, the data rate associated with a traffic source is highly variable. Transactional data is typically transmitted in bursts. Thus, the data rate exhibits a high peak to average ratio. Accordingly, the design of Local Area Networks aimed at supporting data applications has been based on the principle of bandwidth sharing and statistical time multiplexing. In contrast, the data rate associated with the transmission of a video stream is relatively constant; the precise value depends on the particular encoding scheme used and the image quality desired, but it tends to be much higher than the average rate associated with a transactional data source. In particular, CCITT recommendation H.261 specifies video coding and decoding methods for audiovisual services at the rates of p.times.64 Kbits/s, where p is in the range 1 to 30; the MPEG standard specifies a coded representation that can be used for compressing video sequences to bit rates around 1.5 Mbits/s; Intel's DVI video streams have a data rate of 1.2 Mbits/s or higher, depending on the desired video image quality; the successor to MPEG, known as MPEGII, is being developed to provide a wider range of functionality and image quality than its predecessor at rates in the range of 4 to 9 Mbits/s.
Two important observations can be made. The first is that the volume of bits corresponding to a video segment of useful duration is large. A ten minute DVI video segment corresponds to 90 Mbytes. Ten hours correspond to over 5 Gbytes. Thus, video servers for use in systems where shared video information is to be stored must be of relatively high capacity.
The second observation is that the transmission of video data at a certain data rate over a Local Area Network requires the provision of a channel of the same data rate on a continuous basis so as to achieve timely delivery of the data. To support the transmission of multiple independent video streams in a local area environment would require a network which can guarantee the bandwidth required for each video stream, and which has an aggregate bandwidth exceeding that required for the maximum configuration expected.
A typical local area environment comprises a number of user stations connected into a local area network by a shared transmission channel. A network may be viewed as one or more interconnected network segments which each have a shared transmission medium, for physically implementing the shared transmission channel, and one or more stations connected thereto. Data organized into packets may be transmitted on the shared transmission medium according to one of a number of protocols such as Ethernet (IEEE 802.3), token bus (IEEE 802.4), token ring (IEEE 802.5), or FDDI (ANSI X3T9.5). Application programs executed at each station may generate one of at least two types of data: bursty transactional data and stream-oriented video or audio data.
A typical station 10 used in a local area network is shown in FIG. 1. The station 10 is connected to a shared medium 28 of a network segment. The station 10 has a bus 12 to which a CPU 14, a main memory 16 and a disk memory 18 are connected. In addition, an I/O device 20 is connected to the bus 12 which illustratively includes a display device 22, such as a cathode ray tube (CRT) terminal, and a keyboard 24. A network interface circuit 26 connects the bus 12 to the shared transmission medium 28 of the network. The network interface circuit 26 receives data from the bus 12 (e.g., originating from the CPU 14, main memory 16, disk memory 18, I/O device 20, etc.) for transmission over the shared transmission medium 28. In addition, the network interface circuit 26 receives data destined to the station 10 from the shared transmission medium and transmits this data onto the bus 12 (to, e.g., the CPU 14, main memory 16, disk memory 18, I/O device 20, etc.).
The transfer of data between the station 10 and the shared transmission medium 28 may be illustrated using functional layers. As depicted in FIG. 2, the highest layer contains a communication protocol stack including one or more protocols. Illustratively, a protocol is provided for each type of data transmitted and received by the station. The protocol organizes data of the corresponding type into data packets to be transmitted from the station. Similarly, the protocol extracts data of a corresponding type from a received packet.
Associated with each protocol is a queue. Each queue is for storing different types of data packets, such as video data packets and transactional data packets. On the next level, a multiplexer maintains the packets in a corresponding queue of the stack and appropriately multiplexes the packets generated by the various stacks onto a single service access point of the next layer. Conversely, the multiplexer also appropriately dispatches the packets arriving from the access point to the various protocol stacks. Illustratively, the protocol stack, queues and multiplexer may be implemented in the CPU 14 (and, for instance, the main memory 16 and/or disk memory 18) which executes appropriate instructions for performing the respective functions.
The next layer includes a media access controller (MAC). The MAC layer provides access for packets to and from the shared transmission medium. The MAC layer illustratively includes the network interface circuit 26 and appropriate software for implementing a protocol for sharing the shared transmission medium with other stations, such as Ethernet, token ring, token bus, or FDDI. These MAC protocols are briefly examined below as to their ability to differentiate between different types of traffic.
1) IEEE 802.3 (Ethernet)
IEEE 802.3 is devised for a passive bus network structure. It has no concept of traffic types nor priorities. The access algorithm works as follows. Consider a station with a packet scheduled for transmission at a point in time t. If the station senses the channel idle at time t, it initiates the transmission of the packet. If the station senses the channel busy at time t, it monitors the channel until the end-of-carrier appears, and then, following a period of time called the interframe gap, it initiates the transmission of the packet.
Either the transmission of the packet is not interfered with, in which case it is transmitted successfully, or a collision with another packet is detected. In such a case, the transmission of the packet is aborted and the packet is rescheduled for transmission according to a truncated exponential backoff algorithm.
The truncated exponential backoff algorithm is as follows: Consider a station which has just incurred its n.sup.th collision, n=1,2,...,15. Let t.sub.n denote the time when the end-of-carrier corresponding to the collision period is detected. The station reschedules the packet for transmission at the time t.sub.n +ks, where k is an integer selected uniformly in the range [0,2.sup.min{n,10 } -1] and s denotes the slot size. (The slot size must be greater than the maximum roundtrip delay in the network, and has a default value of 51.2 microseconds, or equivalently 512 bit times.) At the 16.sup.th collision, the station stops attempting transmission of the packet.
2) IEEE 802.5 (Token ring)
IEEE 802.5 is a token protocol devised for a ring network. It uses a single token, in the sense that a station that has completed transmission will not issue a new token until the busy token returns to it. Contrary to bus type networks which are passive networks, a ring network is active in the sense that a station's tap is a powered device which regenerates the signal it is relaying. Similarly, a tap is capable of modifying the signal it is relaying. Using this capability, this scheme offers priority access to packets by dynamically assigning a priority value to the token, and by restricting access to the ring to packets of priority equal or higher than the currently assigned value. Restricting the scheme to a single token, while not as efficient as using multiple tokens, simplifies priority and error recovery functions.
3) IEEE 802.4 (Token bus) and FDDI
IEEE 802.4 is devised for a passive bus network in which stations form a logical ring, and use a token passing scheme for access control purposes. The bus, being passive in nature, prevents the use of a prioritized token scheme such as IEEE 802.5. Instead, a timer based access control scheme is employed as described below in detail.
FDDI is a ring network which uses a token passing scheme as well. Since it is a higher bandwidth network in comparison to IEEE 802.5, the scheme could not be restricted to a single token, as this would severely limit the throughput of the network. Thus, a priority access scheme similar to IEEE 802.5 cannot be envisioned. Instead, the timer based access control scheme introduced in IEEE 802.4 is employed.
Both IEEE 802.4 and FDDI differentiate among different types of traffic, and place a limit on the period of time that a station may spend transmitting packets of a given type. More explicitly, eight service classes are defined, labeled 0 through 7 (the higher the label, the higher the priority). (Note that IEEE 802.4 limits the number of classes to 4, numbered 6,4,2,0, with class 6 handled in the same manner as class 7 in FDDI. All other classes in both schemes are otherwise handled in the same manner.) Within a station, each access class acts as a virtual substation in that the token is passed internally from one class to the next, in the order 7,6,5 etc. A time parameter called the token hold time (THT) is assigned to class 7. Each of the other 7 classes is assigned a parameter called the target token rotation time (TRT.sub.i, where i=6,5,...,0). When a station first receives the token, it transmits consecutive packets of class 7 until it has transmitted all such packets, or a period of time equal to THT has elapsed, whichever comes first. For the other classes, the corresponding virtual substation measures the token circulation time, i.e., the time it took the token to return since the last visit to that substation. If the token returned in less than its TRT, then the substation transmits packets of that class until all such packets are transmitted or a period equal to the difference between its TRT and the measured token circulation time has elapsed, whichever comes first; otherwise, the station passes the token to the next substation immediately. The philosophy behind this scheme is clear: upon reception of the token, each station is guaranteed a transmission quota equal to THT for class 7. However, data packets of lower classes can gain access only if the token returns in a period of time below a given threshold. Obviously, if the total transmission time of class 7 data packets in a token cycle exceed all the TRT's, then all lower classes cannot use the channel at all, yielding to the highest priority class 7 traffic. The intention behind the cycle-dependent timing mechanism is that, as the load of class 7 reduces, lower class packets are allowed to access the channel successively starting from the access class with the largest TRT down to the one with the smallest TRT. Note that it can be shown that this cycle-dependent timing mechanism limits the token circulation time at or below twice the largest TRT, provided that the sum of all the THT's for all stations is less than the largest TRT. As a result one can control the access delay at each substation by appropriately setting the largest TRT. This implies that one can support real-time traffic, such as packetized video, as class 7 traffic, while allowing other traffic to share the excess bandwidth. It can also be shown that a class lower than 7 with a larger TRT gets a larger share of the channel bandwidth; and that, depending on the relative values of the TRT's, it is possible for certain classes to be deprived of service.
Each of the aforementioned MAC layer protocols is disadvantageous. The IEEE 802.3 (Ethernet) is very popular and widely deployed, but does not support any prioritization of the different types of transmitted data. Furthermore, most network implementations based on IEEE 802.4 (token ring), IEEE 802.5 (token bus) and ANSI X3T9.5 (FDDI) do not make use of the above-mentioned packet access control or station transmission ordering functions specified in the standards. Thus, most existing networks are incapable of properly allocating bandwidth of the shared transmission channel for delivering streamed video data in a continuous and timely fashion to its destination.
It is therefore an object of the present invention to provide for timely delivery of video data without requiring significant changes to the hardware of the communications network. In particular, it is an object of the present invention to adapt a network so that, according to a station transmission ordering, each station enables packets to access a shared transmission medium according to an packet access control scheme so as to guarantee bandwidth of the shared transmission medium to particular types of packets, such as video, without modifying the stations' hardware.